package com.topcoder.srm519;


public class VerySmoothDecompositions {
	private int MOD = 1000000009;
	
	private int[] primes = new int[]{2, 3, 5, 7, 11, 13};
	private int[][] deco = new int[][]{{2, 0}, {1, 1}, {3, 0}, {0, 2}, {2, 1}, {4, 0}};
	private StringBuilder number;
	
	public int solve(String[] digits) {
		number = new StringBuilder();
		for (String d : digits) number.append(d);

		int[] co = new int[6];
		for (int i=0; i<6; i++) co[i] = divideBy(primes[i]);
		if (!"1".equals(number.toString())) return 0;
		
		int[][] C = new int[co[0]+1][co[1]+1];
		for (int i=0; i<=co[0]; i++)
			for (int j=0; j<=co[1]; j++)
				C[i][j] = 1;
			
		for (int i=0; i<6; i++) {
			for (int j=0; j<=co[0]; j++) {
				for (int k=0; k<=co[1]; k++) {
					if (j>=deco[i][0] && k>=deco[i][1]) {
						C[j][k] = (C[j][k] + C[j-deco[i][0]][k-deco[i][1]]) % MOD;
					}
				}
			}
		}
		
		long result = 0;
//		for (int a14=0; a14<=Math.min(co[0], co[3]); a14++) {
//			for (int a15=0; a15<=Math.min(co[1], co[2]); a15++) {
//				for (int a10=0; a10+a15<=co[2] && a10+a14<=co[0]; a10++) {
//					int p = co[0] - a10 - a14;
//					int q = co[1] - a15;
//					result = (result + C[p][q]) % MOD;
//				}
//			}
//		}
		
		for (int a15=0; a15<=Math.min(co[1], co[2]); a15++) {
			long[] sum = new long[co[0] + 1];
			int q = co[1] - a15;
			sum[0] = C[0][q];
			for (int i=1; i<=co[0]; i++) sum[i] = sum[i-1] + C[i][q];
			
			for (int a14=0; a14<=Math.min(co[0], co[3]); a14++) {
				int maxa10 = Math.min(co[0]-a14, co[2]-a15);
				result += sum[co[0] - a14];
				if (co[0] >= a14 + maxa10 + 1) {
					result -= sum[co[0] - a14 - maxa10 - 1];
				}
			}
		}
		result = (result%MOD + MOD) % MOD;
		
		return (int) result;
	}
	
	private int divideBy(int prime) {
		int co = 0;
		int r = 0;
		
		while (number.length() > 0) {
			StringBuilder quotient = new StringBuilder();
			for (int i=0; i<number.length(); i++) {
				int n = r * 10 + (number.charAt(i) - '0');
				int q = n / prime;
				r = n % prime;
				if (q > 0 || quotient.length() > 0) quotient.append(q);
			}
			if (r==0) {
				number = quotient;
				co++;
			}
			else {
				return co;
			}
		}
		
		return 0;
	}
}
